﻿namespace TowerOfHanoi
{
    /// <summary>
    /// 递归实现汉诺塔
    /// </summary>
    internal class Program
    {
        static int count = 0;
        static void Main(string[] args)
        {
            Console.WriteLine("请输入盘子个数：");
            //好像必须按字符输入再转换成int，不然程序会一直跑下去
            string n = Console.ReadLine();
            int num = int.Parse(n);
            Hanoi(num, 'A', 'B', 'C');
            Console.WriteLine($"共挪动了{count}次");
        }
        /// <summary>
        /// Move函数用于显示挪动
        /// </summary>
        static void Move(char x, char y)
        {
            Console.WriteLine($"挪动{x}-->{y}");
            count++;
        }
        /// <summary>
        /// Hanoi函数用于递归
        /// 把汉诺塔的n个盘子划分成最下面1个和上面n-1个
        /// 上面n-1个划分成最下面1个和上面n-2个
        /// 这样划分下去，问题就变成了每次n-1个和1个，把n-1个看成一个整体，那就是两个盘子
        /// 如果是n-1个和1个盘子的话，只需要把上面n-1个借助C座挪动到B座
        ///                         再把最下面1个挪动到C座
        ///                     再把B座的n-1个借助A座挪动到C座
        /// 这种算法有特例，就是只有1个盘子的时候
        /// </summary>
        static void Hanoi(int n, char a, char b, char c)
        {
            //最后只有一个的话就直接从a挪到c就行了
            if (n == 1)
                Move(a, c);
            else
            {
                Hanoi(n - 1, a, c, b);
                Move(a, c);
                Hanoi(n - 1, b, a, c);
            }


        }
    }
}